package slidingWindowAlgorithm.review4_20;

import java.util.HashMap;
import java.util.Map;

public class Class567 {
    public boolean minWindow(String s, String t) {
        // 需要包含t中的所有字符
        Map<Character, Integer> need = new HashMap<>();
        for(char c : s.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);

        //滑动窗口
        Map<Character, Integer> window = new HashMap<>();

        /*[left, right) 窗口大小：right - left; */
        int left = 0, right = 0; //初始时，窗口不包含任何元素
        int valid = 0;   //字符找齐了，valid++；
        int size = t.length();
        int minLen = size + 1; //包含t的子串不止1个，要求最小的。
        int start = 0;  //最优解的起点；
        while(right < size) {
            /* 右移动right，扩大窗口，寻找可行解 */
            char c = t.charAt(right);
            right++;
            if(need.containsKey(c)) {
                //如果是t中的字符，加入到window中
                window.put(c, window.getOrDefault(c, 0) + 1);
                //例:s->abbbce,t->be,第一次遍历到b时,valid加1,第二次遍历到b时,不会加1,因为
                //window.get(c).equals(need.get(c)) 为false,window.get(c)=2,need.get(c)=1
                if(window.get(c).equals(need.get(c)))
                    valid++;
            }

            /* 找到可行解后，右移动left，缩小窗口，进行优化 */
            int needSize = need.size();
            int size2 = s.length();

            while(valid == needSize) {

                //  CKG TODO 2023/4/20: 关键之处 大的前提是 valid==needSize  共同保证是两个相连的字符串
                if (right-left==size2){
                    return true;
                }
                c = t.charAt(left);
                left++;

                if(need.containsKey(c)) {
                    if(window.get(c).equals(need.get(c)))
                        valid--;
                    window.put(c, window.get(c) - 1);
                }
//                /* 求最优解 [left - 1, right) */
//                if(valid != needSize) {
//                    if(right - left + 1 < minLen) {
//                        start = left - 1;
//                        minLen = right - left + 1;
//                    }
//                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Class567 class567 = new Class567();
        System.out.println(class567.minWindow("ab", "eibcacba"));

    }




}
